#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL INF = 0x3f3f3f3f;
const LL MAX = 2e5 + 5;
struct Node {
    LL data, score;
    bool isred = true;
}a[MAX];
LL T, n;
int isfind(int x)
{
    for(int i = x - 1; i >= 1; i--) {
        if(a[i].data == a[x].data) {
            return i;
        }
    }
    return -1;
}
bool IcanDo(int now, int ago)
{
    //judge ago~now's score and now's score and judge color is the same
    int cnt = 0;
    bool c_flag = a[ago + 1].isred, flag = true;
    for(int i = ago + 1; i < now - 1; i++) {
        if(c_flag != a[i + 1].isred) {
            flag = false;
        }
        cnt += a[i].score;
    }
    if(cnt < a[now].data || flag) {
        return true;
    }
    return false;
}
int main()
{

    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            cin >> a[i].data;
            a[i].score = 0;
            int isf = isfind(i);
            if(isf != -1 && IcanDo(i, isf)) {
                a[i].isred = a[isf].isred;
                a[i].score = a[i].data;
                for(int j = i - 1; j >= isf; j--) {
                    a[j].isred = !a[i].isred;
                    a[j].score = 0;
                }
            }
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            //cout << a[i].score << ' ';
            ans += a[i].score;
        }
        //cout << "ans = ";
        cout << ans << endl;
    }
    return 0;
}
